from typing import List


def partition(arr, low, high):
    i = low - 1  # 最小元素索引
    pivot = arr[high]

    for j in range(low, high):
        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


# 快速排序函数
def quickSort(arr, low, high):
    """
    :param arr: 排序数组
    :param low: 起始索引
    :param high: 结束索引
    :return: None -- sort in-place
    """
    if low < high:
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)


if __name__ == '__main__':
    # nums = [8, 9, 3, 2, 1, 0, 6]
    nums = [8, 6, 9, 7]
    n = len(nums)
    quickSort(nums, 0, n - 1)
    print(nums)
